1. Field of the Invention
This invention relates to a cache controller used for a multi-processor type fault tolerant computer or the like in which each processor has a write back type cache memory, and further relates to fault tolerant computer and a data transfer system at the time of the cache flush in the fault tolerant computer.
2. Description of the Prior Art
FIG. 15 shows a prior art cache controller of the type noted above. The Figure is shown in an article entitled "You will be familiar with 32-bit microprocessor cache", Yokota, "Nikkei Electronics", No.434, pages 159 to 174, Nov. 16, 1987. Referring to the Figure, designated at 1 is a microprocessor, at 2 is a cache controller, at 3 is a cache memory, at 4 is an interface circuit, at 5 is a system bus, at 6 is a main memory, at 7 is an address line, at 8 is a data line, and at 9 is a control line. The cache controller 2 comprises a tag memory 21, a comparator 22, a controller 23 and a bus monitor 24.
The microprocessor 1, tag memory 21, comparator 22, bus monitor 24, cache memory 3 and interface circuit 4 are connected to one another by an address line 7. The microprocessor 1, cache memory 3, and interface circuit 4 are also connected to one another by a data line 8. The microprocessor 1, controller 23, bus monitor 24, cache memory 3 and interface 4 are connected to one another by a control line 9. Further, the controller 23, tag memory 21, controller 23, and cache memory 3 are connected to one another by control lines 9a and 9b. The system bus 5 and bus monitor 24 are connected to each other directly by an address line 7a and control line 9c, that is, not through the interface circuit 4. The memory 21 and comparator 22 are connected to each other by an address controller 7c, and the controller 23 and bus monitor 24 are connected to each other by an address line 7d.
Now, the operation will be described.
The microprocessor 1 supplies a request for accessing the main memory 6 to the tag memory 21 and comparator 22. In tag memory 21, address of data in the cache memory 3 and bits indicative of the nature of the data (such as effectiveness and alteration) are held for each cache block.
A description will be made hereinbelow with reference to FIG. 16 in terms of the case that a request of the microprocessor is a read request. First, a check is executed as to whether there is requested data in the cache memory 3 (1601). If there is an address matched to the tag memory 21, the valid bits of the cache block are checked (1608). If the valid bit of the cache block containing that data is "ON", the data is read out from the cache memory 3 (1607). If the valid bits of the cache block are "OFF", a newest value is read out from the main memory 6 or a different module into the cache block(1606), and also data is supplied to the microprocessor 1 (1607). Meanwhile, if no entry is found in the cache memory 3, a check is executed as to whether there is a vacant block in the cache memory (1602). If there is a vacant block, a block having data required for the block is read out (1606), and also data is supplied to the microprocessor 1 (1607). If there is no vacant block, a substitute block is selected (1603), and modified bit of the selected cache block is checked (1604). If the modified bit is "ON", the pertaining cache block is written back in the main memory 6 (1605). Then, a block having data requested for the written-back cache block is read out (1606), and also data is supplied to the microprocessor 1 (1607). If the modified bit in the substitute block is "OFF", data required for the block are read out from the main memory 6 or a different module (1606), and also data is supplied to the microprocessor 1 (1607).
Secondly, a description will be made hereinbelow with reference to FIG. 17 in terms of the case that a request supplied from the microprocessor 1 is a write request. First, a check is executed as to whether there is request data in the cache memory 3 (1701). If there is an address matched to the tag memory 21, valid bit of that cache block is checked (1709). If the valid bit of the cache block having that data is "ON", modified bit of the cache block is checked (step 1710). If the modified bit is also "ON", the microprocessor 1 writes data in the cache block (1708). If the cache block valid bit is "ON" and the modified bit is "OFF", the modified bit in the cache block is made to be "ON" (1707), and also data is written in the cache memory 3 (1708). If the valid bit of the matched cache block is "OFF", a newest value is read out from the main memory 6 or different module into the same cache block (1706), and after the modified bit is made to be "ON" (1707), data is written (1708). If there is no entry in the cache memory 3, a check is executed as to whether there is a vacant block in the cache memory 3 (1702). If there is a vacant block, a block having data required for the block is read out (1706), and after the modified bit is made to be "ON" (1707), data is written (1708). If there is no vacant block, a substitute block is selected (1703), and the modified bit of the substitute block selected is checked (1704). If there is an "ON" modified bit, that block is written back in the main memory 6 (1705). Then, a block containing data required for the written-back block is read out (1706), and after the modified bit is made to be "ON" (1707), the data is written (1708). In the case that the modified bit of the substitute block is made to be "OFF", the data required for that block is read out from the main memory 6 or a different module (1706), and after the modified bit is made to be "ON" (1707), data is written (1708).
The bus monitor 24 includes an internal tag memory which is matched to the tag memory 21. The operation of other microprocessors on the system bus 5 is monitored. If a bus cycle due to a read error, a write hit or a write error is detected, the pertinent address is compared to the contents of the internal tag memory.
In case of a read error, if the tag memory matches the address and the valid and modified bits are respectively "ON", the cache controller 2 provides data to the module requiring that cache block and/or the main memory 6, and then the modified bit is made to be "OFF". If the modified bit is "OFF", the cache controller executes no operation.
In case of a write hit, if the tag memory matches the address, a valid bit of that cache block is made to be "OFF".
In case of a write error, if the tag memory matches the address and there are "ON" valid and modified bits, as in the case of lead error, data is provided, and then the "ON" valid bit of that block is set to be "OFF".
Among the above situations, in case when a updated cache block is substituted and a case when updated data is referred to by a different microprocessor, a recovery point is set. The term "recovery point" means a point, up to which the routine goes back for restoring and resuming the process in cases where an error occurs in the microprocessor 1 during the processing. At the recovery point, the controller 23 checks all the modified bits of the tag memory 21, and all the updated cache blocks in the cache memory 3 are written back in the main memory 6 (which will be referred to as a cache flush). When the writing-back is completed, the modified bits of the cache block are made to be "OFF".
On the other hand, FIG. 18 is a block diagram showing an arrangement of a conventional fault tolerant computer exemplified by description in U.S. Pat. No. 4,819,154. In the illustration, 1801 represents the same processor module including a processor for executing both user and supervisor programs, 1802 designates a system bus doubled in order to improve the reliability and throughput, and 1803 denotes a memory module for storing program/data of user/supervisor. Although the system bus 1802 is sufficient to be constructed as a single bus, it is arranged to be doubled so as to prevent stop of the operation of the entire system due to troubles in the bus to improve the system throughput. Although being illustrated by one line in FIG. 18, the system bus 1802 is actually constructed as a multi-wire bus comprising a number of data and signal lines. The data to be stored in the memory module is also stored in physically different two memory modules for the countermeasures against fault.
FIG. 19 shows a more detailed arrangement of the processor module. In the illustration, 1901 represents a memory managing unit for converting a virtual address into a physical address, 1902 designates a processor for implementing user/supervisor programs, 1903 depicts a local address bus, 1904 denotes a local data bus, 1905 indicates a bus adapter for checking the parity of the data from a cache memory to the local data bus to produce a byte parity with respect to the data from the local data bus to the cache memory, 1906 is a cache address bus. Further, 1907 represents an internal control sequencer, 1908 designates a cache memory which is not of the write-through type (that is, a write-back type cache memory), 1909 depicts a cache data bus, 1910 denotes a block-state memory (having a similar structure to the tag memory 21 in the FIG. 15), 1911 is an external control sequencer, 1912 indicates a data bus, and 1913 represents a system bus interface. The processor module completely has the same structure and is treated similarly.
FIG. 20 is an illustration of a more detailed arrangement of the memory module. In the illustration, 2001 represents a system bus interface, 2002 depicts an internal address bus, 2003 designates encoder/decoder, 2004 is a control sequencer for producing a control signal and a synchronizing signal for sequencing the memory module, 2005 is an address detector/producer for decoding address to detect the address to which the corresponding memory module is responsive, 2006 indicates a RAM timing/control unit for producing a row address, column address and a chip selection signal, and 2007 is a RAM array.
Secondly, a description will be made hereinbelow in terms of the operation. The memory access request from the processor 1902 is processed in the internal control sequencer 1907. The internal control sequencer 1907 checks, with reference to the block-state memory 1910, whether the requested data is present in the cache memory 1908. In the case that the request of the processor 1902 is a read request and the requested data is present in the cache memory 1908, the data is immediately supplied from the cache memory 1908 to the processor 1902. In cases where the requested data is absent in the cache memory 1908 or the data is invalid, after the address conversion is effected in the memory managing unit 1901, the address is transferred through the external control sequencer 1911 and the system bus interface 1913 to the memory module. The memory module is responsive to the transfer of the cache block including the requested data. The transferred cache block is supplied to the processor 1902 and, at the same time, stored in the cache memory 1908.
Let it be assumed that the request of the processor 1902 is a write request and the requested data is present in the cache memory 1908. In the case that the cache block including the data has already been updated, the writing is performed immediately. On the other hand, in the case that the cache block is not updated, the bit in the block-state memory 1910 which corresponds to the cache block and which indicates the completion of the update is changed before performing the writing operation. Further, in cases where the requested data is absent in the cache memory 1908 or the data is invalid, after the address conversion in the memory managing unit 1901, the address is supplied through the system bus interface 1913 to the memory module. The memory module is responsive to the transfer of the block including the requested data. The supplied data block is updated after supplied to the processor 1902 and then written in the cache memory 1908. At that time, the block-state memory 1910 is also updated.
Since the prior are apparatus has the cache memory 1908 which is not of the write-through type (that is, which is of the write-back type), the data in the cache memory is not always coincident with (or matched to) the data in the memory module. In addition, as recovering countermeasures against the occurrence of trouble is taken a method in which the state that the system operates normally is kept (which is referred to as a recovery point) so that the process is resumed from the latest recovery point in the memory module in response to the occurrence of trouble. Accordingly, in the case that the recovery point is set, it is necessary that the internal register information in the processor is written in the cache memory and all the cache blocks updated locally in the cache memory are written in the memory module (which is referred to as a cache flush) so that the cache memory is coincident in data with the memory module. In the prior art apparatus, in response to the overflow in the context and cache memory, the occurrence of the overflow is detected to perform the cache flush operation.
The operation effected at the time of the cache flush will be described hereinbelow with reference to FIG. 21. In response to the occurrence of the cache flush, the processor 1902 starts the cache flush operation with respect to the internal control sequencer 1908. The internal control sequencer 1908, at every entry of the block-state memory 1910, fetches the bit representative of whether the cache block is updated or not (2101) and checks it by means of the comparator within the internal control sequencer 1908 (2102). If the modified bit is "ON", the data block corresponding to that entry is fetched from the cache memory 1908 (2103) and is transferred through the system bus interface (1913) to the memory module (2104). After the transfer, the flush address is incremented (2105) so as to be compared with the termination address (2106). If not exceeding the termination address, the operational flow returns to the process 2101 to repeat the processes. If the modified bit of the cache block is "OFF", the flush address is incremented (2105). If not exceeding the termination address, the operational flow returns to the process 2101 to repeat the processes.
In the prior art apparatus, the above-mentioned cache flush operation is performed in unit of the doubled memory modules. The cache flush operation is effected two times so that correct data is always presented in one of the memory modules. First, the cache flush operation is performed with respect to one of the memory modules. In the cache flush operation, the cache block is directly written through the system bus interface 2001 or encoder/decoder 2003 to the RAM array 2007. In the system bus interface 2001 or encoder/decoder 2003, the parity check, error detection and correction process are performed with respect to the data block. When the first cache flush is succeeded, the cache flush is performed with respect to the other memory module. When the second cache flush operation is normally completed, the processor module resumes the process before the cache flush.
If a trouble occurs in the first cache flush operation, the process is resumed from the newest recovery point which has previously been kept in the other memory module. For the recovery, the memory module in which the trouble occurs copies the contents of the one memory module. In response to a trouble occurring in the second cache flush operation, the process is implemented using the data within the memory module which has been updated by the first cache flush. In case that a trouble generates during the second cache flush, a storage area is reassigned on a different memory module and the contents are copied in that area for the recovery.
With the prior art cache controller having the construction as described above, when a recovery point is set, it is necessary to execute once a retrieval of cache address tags for writing back all the updated cache blocks in the cache memory. Consequently, a processing of writing back all the updated cache blocks, i.e., a cache flush process, takes a long time.
Similarly, since the prior art fault tolerant computer is arranged as described above so that all the updated cache blocks in the, cache memory are transferred to the memory module in response to start of the cache flush operation, the updated cache block is required to be searched by retrieving all the entries of the block-state memory, thereby taking a long time for the cache flush operation.
In addition, since in the conventional apparatus the setting interval of the recovery points is unspecified, difficulty is encountered to specify the time required until resuming the process through the recovery after the detection of a trouble and hence to keep the real time operation.
Furthermore, in the conventional apparatus the data transfer from the cache memory is required to be performed two times in the cache flush operation because of being transferred to the two memory modules, and therefore there is a problem that the bus load is increased to sacrifice the system performance.
Moreover, since in the prior art apparatus all the cache blocks updated in the cache flush operation are transferred to the memory module, it is required to repeatedly perform the transfer transaction at every cache block, and hence there is a problem that the system bus load is increased so as to sacrifice the system performance.